package leetcode.editor.cn;
//一条包含字母 A-Z 的消息通过以下映射进行了 编码     ：
// 1123 1 1 2 3   11 2 3    1 12 3  1 1 23  11 23
// 1
// 1 1   11
// 1 1 2    11 2    1 12
//'A' -> "1"
//'B' -> "2"
//...
//'Z' -> "26" 
//
// 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为： 
//
// 
// "AAJF" ，将消息分组为 (1 1 10 6) 
// "KJF" ，将消息分组为 (11 10 6) 
// 
//
// 注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。 
//
// 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。 
//
// 题目数据保证答案肯定是一个 32 位 的整数。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "12"
//输出：2
//解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
// 
//
// 示例 2： 
//
// 
//输入：s = "226"
//输出：3
//解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
// 
//
// 示例 3： 
//
// 
//输入：s = "06"
//输出：0
//解释："06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 100 
// s 只包含数字，并且可能包含前导零。 
// 
//
// Related Topics 字符串 动态规划 👍 1477 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution260 {

    public int numDecodings1(String s) {
        int length = s.length();
        if (s.charAt(0) == '0') return 0;
        int[] dp = new int[length];
        dp[0] = 1;

        for (int i = 1; i < length; i++) {
            char c = s.charAt(i);
            char d = s.charAt(i - 1);
            if (c == '0') {
                if (d != '1' && d != '2') return 0;
                dp[i] = i >= 2 ? dp[i - 2] : 1;
            } else {
                dp[i] = dp[i - 1];
                if (d != '0') {
                    int time = (d - '0') * 10 + (c - '0');
                    if (time <= 26) {
                        dp[i] = i >= 2 ? dp[i - 2] + dp[i - 1] : dp[i - 1] + 1;
                    }
                }
            }
        }
        return dp[length - 1];
    }

    /**
     * 对于字符串 s 的任意位置 i 而言，其存在三种情况：
     * <p>
     * 只能由位置 i 的单独作为一个 item，设为 a，转移的前提是 a 的数值范围为 [1,9]，转移逻辑为 f[i]=f[i−1]。
     * 只能由位置 i 的与前一位置（i-1）共同作为一个 item，设为 b，转移的前提是 b 的数值范围为 [10,26]，转移逻辑为 f[i]=f[i−2]。
     * 位置 i 既能作为独立 item 也能与上一位置形成 item，转移逻辑为 f[i]=f[i−1]+f[i−2]。
     * 因此，我们有如下转移方程：

     * f[i]=f[i−1],1⩽a≤9
     * f[i]=f[i−2],10⩽b⩽26
     * f[i]=f[i−1]+f[i−2],1⩽a≤9,10⩽b⩽26
     *
     * 其他细节：由于题目存在前导零，而前导零属于无效 item。
     * 可以进行特判，但个人习惯往字符串头部追加空格作为哨兵，
     * 追加空格既可以避免讨论前导零，也能使下标从 1 开始，简化 f[i-1] 等负数下标的判断。
     *
     * @param s
     * @return
     */
    public int numDecodings(String s) {
        int n = s.length();
        s = " " + s;
        char[] cs = s.toCharArray();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            // a : 代表「当前位置」单独形成 item
            // b : 代表「当前位置」与「前一位置」共同形成 item
            int a = cs[i] - '0', b = (cs[i - 1] - '0') * 10 + (cs[i] - '0');
            // 如果 a 属于有效值，那么 f[i] 可以由 f[i - 1] 转移过来
            if (1 <= a && a <= 9) f[i] = f[i - 1];
            // 如果 b 属于有效值，那么 f[i] 可以由 f[i - 2] 或者 f[i - 1] & f[i - 2] 转移过来
            if (10 <= b && b <= 26) f[i] += f[i - 2];
        }
        return f[n];
    }
}
//leetcode submit region end(Prohibit modification and deletion)
